package algorithm.leetcode.I1to100;


/**
 * 排列序列
 */

public class Q60 {

    int index = 0;
    String res;

    public String getPermutation(int n, int k) {
        dfs(new boolean[n], new StringBuilder(""), n, k);
        return res;
    }

    public void dfs(boolean[] isUsed,
                    StringBuilder curr,
                    int n,
                    int k) {

        if (res != null) return;
        if (curr.length() == n) {
            if (++index == k) {
                res = curr.toString();
            }
            return;
        }

        for (int i = 0; i < isUsed.length; i++) {
            if (!isUsed[i]) {
                isUsed[i] = true;
                curr.append(i+1);
                dfs(isUsed, curr, n, k);
                curr.deleteCharAt(curr.length()-1);
                isUsed[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Q60 q60 = new Q60();
        q60.getPermutation(3,3);

    }


}
